package MAIN;
//笔试强训第24天
//选择题
/*将N条长度均为M的有序链表进行合并，合并后的链表也保持有序，时间复杂度为O(N*M*logN)，
* 1.建立一个长度为N的最大堆/最小堆，时间复杂度为O(N)  2.依次从最小堆中取出堆顶元素，此时
* 堆顶就是当前集合的最小值，将链表的其他元素放进堆中，调整堆的时间复杂度（O(logN)），总共
* 还需要入堆的元素个数，O(N*M*logN)。3.总共建堆+不算调整堆（不断取出堆顶元素）O(N)+O(N*M*logN)*/
/*大小为n的循环队列中，任意时刻队列中的元素个数为：(队首 - 队尾 + n + 1) % n  （n是元素个数）*/
/*在二叉树中，边长=总结点个数 - 1  */
/*要分清二叉搜索树和大根堆/小根堆，大根堆和小根堆是层序遍历可以得到一个有序的序列，而二叉搜索树是
* 中序遍历后可以得到一个有序序列。*/
/*重建堆过程中进行关键字的比较，比较次数算的是左右孩子进行比较，之后和父亲节点比较，然后调整*/
/*进行快速排序，不可能是快排的第n趟的排序结果....  结论：每次进行一次快排，标定点一定在最终位置。
* 进行了两次快排，至少有两个元素是在最终位置的.....*/
/*堆排时间复杂度是稳定的O(N*logN), 原地堆排序的空间复杂度是O(1)*/

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.Scanner;

//编程题

class Node1 {
    public int x;
    public int y;
    public Node1(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main24 {
    //迷宫问题
    //每一个位置有四个方向，可以走的方向：没有越界，没有障碍，之前没有走过
    //搜索：当前位置(x，y)是否越界，(x,y)之前是否走过，(x,y)是否有障碍
    // 如果没有走过，没有越界，没有障碍：
    //1. 把当前位置保存到路径中  2.(x,y)是右下角，出口位置：一条新的路径产生
    //然后判断新的路径是都为更短路径，如果是更短路径，更新路径，
    //3. 继续搜索(x,y)四个方向    4.把当前位置从路径中删除，寻找新的路径

    //mat：迷宫矩阵，row，col
    //x，y：当前位置
    //book：标记矩阵，标记当前位置是否走过
    //path：保存当前路径的每一个位置
    //minPath：保存最短路径
    public static void getPath(int[][] mat, int row, int col, int x, int y, int[][] book,
                               ArrayList<Node1> path, ArrayList<Node1> minPath) {
        //判断(x,y)是否越界，是否走过，是否有障碍
        if (x < 0 || x >= row || y < 0 || y >= col
                || book[x][y] == 1 || mat[x][y] == 1)
            return;
        //把当前位置存入路径中
        path.add(new Node1(x,y));
        //标记当前位置
        book[x][y] = 1;
        //判断当前位置是否为出口
        if (x == row -1 && y == col - 1) {
            //一条新的路径产生
            //判断这条路径是否为更短的路径
            if (minPath.isEmpty() || path.size() < minPath.size()) {
                //就说明这条路径是更短的路径，此时更新更短路径
                minPath.clear();
                for (Node1 n : path) {
                    minPath.add(n);
                }
            }
        }
        //继续搜索（x，y）的上下左右四个方向
        getPath(mat,row,col,x + 1,y,book,path,minPath);
        getPath(mat,row,col,x - 1,y,book,path,minPath);
        getPath(mat,row,col,x,y - 1,book,path,minPath);
        getPath(mat,row,col,x,y + 1,book,path,minPath);
        //递归回退之后，说明这条路径走不通，要把条路径删除
        //把当前位置从路径中删除，寻找新的路径
        path.remove(path.size() - 1);
        //删除当前路径，如果回退，就说明这条路径是不通的，此时需要删除当前路径，下次还可以走这个节点
        book[x][y] = 0;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String str = scan.nextLine();
            String[] strings = str.split(" ");
            int row = Integer.parseInt(strings[0]);
            int col = Integer.parseInt(strings[1]);
            //创建迷宫矩阵
            int[][] mat = new int[row][col];
            //读入迷宫数据
            for (int i = 0; i < row; i++) {
                str = scan.nextLine();
                strings = str.split(" ");
                for (int j = 0; j < col; j++) {
                    mat[i][j] = Integer.parseInt(strings[j]);
                }
            }
            //搜索最短路径
            ArrayList<Node1> path = new ArrayList<>();
            ArrayList<Node1> minPath = new ArrayList<>();
            int[][] book = new int[row][col];
            getPath(mat,row,col,0,0,book,path,minPath);

            //打印最短路径
            for (Node1 n : minPath) {
                System.out.println("(" + n.x + "," + n.y + ")");
            }
        }
    }
    //年终奖
    public int getMost(int[][] board) {
        int row = board.length;
        int col = board[0].length;
        //处理第一行
        for (int i = 1; i < col; i++) {
            board[0][i] += board[0][i-1];
        }
        //处理第一列
        for (int i = 1; i < row; i++) {
            board[i][0] += board[i-1][0];
        }
        //处理剩余位置
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                //状态方程
                //F(i,j) = max(F(i-1,j),F(i,j-1)) + board[i][j]
                board[i][j] = Math.max(board[i-1][j],board[i][j-1]);
            }
        }
        return board[row-1][col -1];
    }

}
